МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ «ЛЬВІВСЬКА ПОЛІТЕХНІКА» Кафедра САПР ЗВІТ про виконання лабораторної роботи №2 на тему: «МЕТОДИ ОПТИМАЛЬНОГО КОДУВАННЯ» З курсу «Проблемно-орієнтовані методи та засоби комп’ютерних інформаційних технологій» МЕТА РОБОТИ Мета роботи – отримати практичні навики використання методів оптимального кодування. КОРОТКІ ТЕОРЕТИЧНІ ВІДОМОСТІ Метод Шеннона-Фано В цьому методі для кожного символа формується бітовий код, довжина якого залежить від частоти появи символа. Чим менша частота, тим довший код. Визначення частоти (ймовірності) символа буває статичне (на основі таблиці даних) та динамічне (коли відомості про ймовірність появи символів визначаються на основі обробки потоку даних). Статичний варіант використовується в архіваторах ARK, PKZIP. Кодування здійснюється таким чином (рис. 1): Всі символи записуються в таблицю по зменшенню їх частоти. Потім вони поділяються на дві групи так, щоб суми частот для отриманих груп були максимально близькі. Для першої групи перший біт коду встановлюється рівним 1, а для другої – 0. Потім групи знову поділяємо на дві і визначаємо наступні розряди коду. Процес продовжується поки в групі не залишиться тільки один символ. Номер Символ Частота Код 1 a 10 11 2 b 8 10 --------------------------------------------------------- 3 c 6 011 4 d 5 010 5 e 4 001 6 f 3 000 Рис. 1. Кодування Шеннона-Фано неоднозначне. В залежності від варіанту поділу на групи (при однаковій різниці частот між ними) будуть отримані різні коди для символів (рис. 2). Символ Частота Код Символ Частота Код с 22 11 с 22 11 e 20 101 e 20 10 h 16 100 -------------------------------------------- ----------------------------------------------- h 16 011 i 16 011 і 16 010 a 10 010 a 10 001 k 10 001 k 10 0001 m 4 0001 m 4 00001 b 2 0000 b 2 00000 Рис. 2. Можливий варіант програмної реалізації методу базується на формуванні і обробці такої таблиці Nгр Np Nk S Код  1 1 2 18 1   3 6 18 0  2 1 1 10 11   2 2 8 10  3 3 4 11 01   5 6 7 00  4 3 3 6 011   4 4 5 010  5 5 5 4 001   6 6 3 000   Ця таблиця забезпечує зручний запис алгоритму поділу на підгрупи і формування кодів. Перша група (Nгр=1) складається з двох підгруп: перша - починається з першого символа (Np=1) і закінчується другим (Nк=2), друга – починається з третього символа (Nр=3) і закінчується шостим (Nк=6). Сума частот першої підгрупи S=18, другої S=18. Друга група (Nгр=2) формується в результаті поділу першої підгрупи з першої групи і складається теж з двох підгруп: перша – починається з першого символа (Nр=1) і ним закінчується (Nк=1), друга – починається другим символом (Nр=2) і ним закінчується (Nк=2). Третя група описує процес поділу другої підгрупи з першої групи. Процуес продовжується до тих пір поки кожна підгрупа не буде складатися тільки з одного символа (Nр=Nк). Відповідний новий біт коду кожної групи визначається таким чином: для першої підгрупи він встановлюється рівним одиниці, а для другої підгрупи – нулю. Метод Хаффмана. Метод полягає в побудові кодового дерева Хаффмана, положення символа на якому визначається частотою (ймовірністю) його появи. Реалізація методу здійснюється по таких кроках: Всім символам ставиться у відповідність одна з вершин дерева. Об’єднуємо дві вершини з мінімальними частотами і для нової вершини вказуємо сумарну частоту. Переходимо на пункт 2, доки не об’єднаємо всі вершини. Обходимо дерево і визначаємо розряди коду по такому правилу: перехід вліво – розряд =1, перехід вправо – розряд = 0 (рис.3). Для програмної реалізації методу можна використати таку таблицю c 22 22 22 26 32 42 58 100 01 e 20 20 20 22 26 32 42 00 h 16 16 16 20 22 26 ...